<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8">
        <meta name="viewport" content="width=device-width,initial-scale=1.0">
        <meta http-equiv="X-UA-Compatible" content="IE-edge,chrome=1">
        <title>对数据规模有一个概念</title>
    </head>
    <body>
        <div>
            <h1>数据规模的概念</h1>
            <h3>如果要想在1s之内解决问题（最好在往下除以10）：</h3>
            <div>
                O(n^2)的算法可以处理大约10^4级别的数据；
            </div>
            <div>
                O(n)的算法可以处理大约10^8级别的数据；
            </div>
            <div>
                O(nlogn)的算法可以处理大约10^7级别的数据；
            </div>
            <div>------------------------------</div>
            <h3>空间复杂度</h3>
            <div>多开一个辅助的数组：O(n)</div>
            <div>多开一个辅助的二维数组:O(n^2)</div>
            <div>多开常数空间:O(1)</div>
            <div>
                递归调用是有空间代价的（递归的深度是多少，整个递归过程所占的空间就是多少）
            </div>
        </div>

        <pre  class="language-JavaScript">
            <code>
                function test1() {
                    for(let i = 1; i <= 9; i ++) {
                        let n = Math.pow(10, i);
                        let startTime = new Date().getTime();
                        let sum = 0;
                        for(let j = 0; j < n; j ++) {
                            sum += j;
                        }
                        let endTime = new Date().getTime();
                        console.log("10^" + i + " : " + ((endTime - startTime) / 1000.0) + " s");
                    }
                }
                test1();
    
                function hello(n) { //O(nlog(n))
                    for(let sz = 1; sz < n; sz += sz) {
                        for(let i = 1; i < n; i ++) {
                            console.log(sz, i)
                        }
                    }
                }
            </code>
        </pre>
        <script>
            function test1() {
                for(let i = 1; i <= 9; i ++) {
                    let n = Math.pow(10, i);
                    let startTime = new Date().getTime();
                    let sum = 0;
                    for(let j = 0; j < n; j ++) {
                        sum += j;
                    }
                    let endTime = new Date().getTime();
                    console.log("10^" + i + " : " + ((endTime - startTime) / 1000.0) + " s");
                }
            }
            test1();

            function hello(n) { //O(nlog(n))
                for(let sz = 1; sz < n; sz += sz) {
                    for(let i = 1; i < n; i ++) {
                        console.log(sz, i)
                    }
                }
            }
        </script>
    </body>
</html>